package problem300;

//300.最长递增子序列
//https://leetcode.cn/problems/longest-increasing-subsequence/

class Solution {
    int n;
    int[] dp;
    public int lengthOfLIS(int[] nums) {
        n = nums.length;
        dp = new int[n];
        int ret = 1;
        for(int i = 0; i<n; i++) ret = Math.max(ret,dfs(nums, i));
        return ret;
    }
    public int dfs(int[] nums, int u) {
        if(dp[u] != 0) return dp[u];

        if(u == 0) {
            return 1;
        }

        int len = 1;
        for(int i = u-1; i>=0; i--) {
            if(nums[i] < nums[u]) {
                len = Math.max(dfs(nums, i) + 1, len);
            }
        }
        dp[u] = len;
        return len;
    }
}